package DFS;

/**
 * 判断一个图是不是一个二分图，即所有的link连接的节点可以被分为两类
 * 没有冲突
 */
public class BipartionDetection {
    private Graph graph;
    private boolean[] visited;
    private int[] colors;
    private boolean isBipartite = true;

    public BipartionDetection(Graph graph) {
        this.graph = graph;
        this.visited = new boolean[graph.getVertexNum()];
        this.colors = new int[graph.getVertexNum()];
        for (int i = 0; i < this.colors.length; i++) {
            this.colors[i] = -1;
        }
        for (int v = 0; v < graph.getVertexNum(); v++) {
            if (!this.visited[v]) {
                if (!dfs(v, 0)) {
                    isBipartite = false;
                    break;
                }
            }
        }
    }

    private boolean dfs(int v, int color) {
        this.visited[v] = true;
        this.colors[v] = color;
        for (int w : graph.adj(v)) {
            if (!this.visited[w]) {
                if (!dfs(w, 1 - color)) {
                    return false;
                }
            } else if (colors[w] == colors[v]) {
                return false;
            }
        }
        return true;
    }

    public boolean isBipartite() {
        return this.isBipartite;
    }

    public int[] colors() {
        return colors;
    }

    public static void main(String[] a) {
        Graph graph = new Graph("gDfs.txt");
        BipartionDetection bd = new BipartionDetection(graph);
        System.out.println(bd.isBipartite());

        Graph graph2 = new Graph("bipGraph.txt");
        BipartionDetection bd2 = new BipartionDetection(graph2);
        System.out.println(bd2.isBipartite());

        Graph graph3 = new Graph("notBipGraph.txt");
        BipartionDetection bd3 = new BipartionDetection(graph3);
        System.out.println(bd3.isBipartite());
    }
}
